package com.study.daily.algozuo.y2021.m12.day1209;

/**
 * @descriptions: Code01_KMP
 * @author: Tom
 * @date: 2021/12/9 下午 03:17
 * @version: 1.0
 */
public class Code01_KMP {
    public static void main(String[] args) {
        Code01_KMP cp = new Code01_KMP();
        String s1 = "01234567";
        String s2 = "456";
        System.out.println(cp.kmp(s1, s2));
    }

    public int kmp(String s1, String s2){
        char[] str1 = s1.toCharArray();
        char[] str2 = s2.toCharArray();
        int i = 0, j = 0;
        int[] nexts = getNextArray(s2);
        while(i < str1.length && j < str2.length){
            if(str1[i] == str2[j]){
                i++;
                j++;
            } else if(nexts[j] == -1){
                i++;
            } else {
                j = nexts[j];
            }
        }
        return j == str2.length ? (i - j): -1;
    }
    public int[] getNextArray(String s){
        if(s.length() == 1){
            return new int[]{-1};
        }
        int N = s.length();
        int[] nexts = new int[N];
        nexts[0] = -1;
        nexts[1] = 0;

        int i = 2;
        int cn = 0;
        while(i < N){
            if(s.charAt(cn) == s.charAt(i-1)){
                nexts[i++] = ++cn;
            } else if(nexts[cn] > 0){
                cn = nexts[cn];
            } else {
                nexts[i++] = 0;
            }
        }
        return nexts;
    }
}
